class Nonogram:
    """
    以数织图    （状态压缩，全排列——可改动态规划，回溯，剪枝
    """

    def __init__(self):
        self.N: int = int(input("行数："))
        """ 方阵大小 """

        self.rows: list[list[int]] = [[0]] * self.N
        """ 初始填入的行信息 """

        self.cols: list[list[int]] = [[0]] * self.N
        """ 初始填入的列信息 """

        for i in range(self.N):
            temp = input(f"输入第{i + 1}行:\t")
            self.rows[i] = [int(n.strip()) for n in temp.strip().split(" ")]
        for i in range(self.N):
            temp = input(f"输入第{i + 1}列\t")
            self.cols[i] = [int(n.strip()) for n in temp.strip().split(" ")]

        # self.N: int = 10
        # self.cols = [[8], [2, 1, 1], [1, 3, 1, 1], [1, 1, 1, 1], [1, 5, 1], [2, 2, 1], [6, 1], [1, 2], [4, 4], [1, 3]]
        # self.rows = [[5, 1],
        #              [2, 2, 2],
        #              [1, 1, 1],
        #              [1, 3, 4],
        #              [1, 1, 1, 1, 1],
        #              [1, 1, 1, 1, 2],
        #              [1, 3, 1],
        #              [6, 1],
        #              [1, 2],
        #              [7]]

        self.match = (2 ** self.N) - 1
        """ 对于一行全涂色后并压缩 """

        self.probRows: list[list[int]] = []
        """ 各行可能的行组合 """

        self.probCols: list[list[int]] = []
        """ 各列可能的列组合 """

        self.defiRow: list[int] = []
        """ 各行确定要涂色的方案 """

        self.defiCol: list[int] = []
        """ 各列确定要涂色的方案 """

        self.colsCondition: list[set[int]] = []
        """ 各列可能的列组合，用于回溯剪枝 """

        self.ans: list = []
        """ 结果集，不唯一 """

        self.alternative: bool = True
        """ 当前选择是否具有可行性，用于回溯剪枝 """

        self.test: int = 0
        """ 统计回溯时一共进行了多少次选择 """

    def run(self):
        for col in self.cols:
            self.probCols.append(self.__explainNum(col))
        for row in self.rows:
            self.probRows.append(self.__explainNum(row))
        for probRow in self.probRows:
            self.defiRow.append(self.__definitely(probRow))
        for probCol in self.probCols:
            self.defiCol.append(self.__definitely(probCol))
        self.__shiftData()
        self.colsCondition: list[set[int]] = [set(probCol) for probCol in self.probCols]
        self.defiAnswer()
        self.printAns()

    def printAns(self):
        """
        将计算得到的结果打印
        """
        print(f"一共进行了了{self.test}次尝试")
        for matrix in self.ans:
            for item in matrix:
                temp = ""
                row = 2 ** (self.N - 1)
                for i in range(self.N):
                    temp += "⬜" if item & row != 0 else "⬛"
                    row //= 2
                print(temp)

    def check(self, arr: list[int]) -> bool:
        """
        检查该组合是否符合列的要求
        :param arr: 从每一行待取组合中取出一个并组成的一个结果
        :return: 是否符合要求
        """
        trans = self.__transform(arr)
        flag = True
        for checked, checkSet in zip(trans, self.colsCondition):
            flag &= (checked in checkSet)
        return flag

    def eliminateRow(self, high: int, row: int) -> list[set[int]]:
        """
        针对选择的当前行，消除掉没有可能的列
        :param high: 当前的行高，由于是从上往下选择的，所以要用N减去该值（例如传入第2行，则需要进行对比列的次高- 每一列）
        :param row: 当天填入的行
        :return: 针对当前选择的行，排除每列的不可选择的组合
        """
        ans = [set()] * self.N
        shift = 2 ** (self.N - high - 1)
        cur = 2 ** (self.N - 1)
        # 是否存在没有可选项的一列
        flag = True
        for cycle, colCondition in enumerate(self.colsCondition):
            temp = set()
            for check in colCondition:
                # 列与当前选择的行              待选的行与与之匹配的列，以上两个均能定位到一个格子，要求其涂色情况相同
                if (check & shift == shift) != (row & cur == cur):
                    # 不同则需要取消掉该列的待选资格
                    temp.add(check)
            colCondition.difference_update(temp)
            flag &= len(colCondition) != 0
            ans[cycle] = temp
            cur //= 2
        self.alternative = flag
        return ans

    def defiAnswer(self, high: int = 0, step=None) -> None:
        """
        深度遍历行，组合可能的结果并进行校验，校验成功即放入结果集当中
        """
        if step is None:
            step = []
        if high == self.N:
            if self.check(step):
                self.ans.append(step.copy())
            return
        for probRow in self.probRows[high]:
            # 在回溯的同时时刻更新列待选，对于待选择的行，与之不匹配的列要取消其候选资格
            self.test += 1
            eliminate = self.eliminateRow(high, probRow)
            step.append(probRow)
            # 若是对于已经选择了的行，没有与之匹配的列选项，则说明是一次失败的选择，直接结束
            if self.alternative:
                self.defiAnswer(high + 1, step)
            step.pop()
            for cycle, colCondition in enumerate(self.colsCondition):
                colCondition.update(eliminate[cycle])

    def __shiftData(self):
        """
        再次过滤待选的行 和 列的组合
        :return:
        """
        # 将每列都必须要涂色的格子转化为每行必须涂色的格子
        rowFilters = self.__transform(self.defiCol)
        # 对所有行待选进行过滤，过滤掉的条件就是列转化来要必须涂色的格子没有完全进行涂色
        for i in range(len(rowFilters)):
            if rowFilters[i] == 0:
                continue
            self.probRows[i] = list(filter(lambda x: (rowFilters[i] & x == rowFilters[i]), self.probRows[i]))

        # 同上
        colFilters = self.__transform(self.defiRow)
        for i in range(len(colFilters)):
            if colFilters[i] == 0:
                continue
            self.probCols[i] = list(filter(lambda x: (colFilters[i] & x == colFilters[i]), self.probCols[i]))

    def __transform(self, matrix: list[int]) -> list[int]:
        """
        将该方阵旋转90°并输出（行向量组成的方阵拆为列向量并输出
        :param matrix:
        :return: 旋转90°后的方阵
        """
        ans = [0] * self.N
        row = 2 ** (self.N - 1)
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                ans[i] *= 2
                ans[i] += (1 if matrix[j] & row == row else 0)
            row //= 2
        return ans

    def __definitely(self, choose: list[int]) -> int:
        """
        将可能的组合取并，得出一定要填入的格子，同理也可以将可能的组合取交，得到一定不能填入的格子
        :param choose: 可能的组合
        :return: 一定要填入
        """
        ans = self.match
        for i in choose:
            if ans == 0:
                break
            ans &= i
        return ans

    def __explainNum(self, arr: list[int]):
        """
        根据传入的数获取可能的所有组合
        :param arr: 一个描述该行（列 填入单元格连续情况的数组，例如：填入一个数 8 则说明该行（列有且仅有一个连续8个格子涂色；
        填入两个数 2 3，则说明该行（列 有一个连续两个格子涂色，有一个连续三个格子涂色，并且两个连续中间有至少一个格子不涂色
        :return: 所有可能的涂色组合
        """
        if sum(arr) + len(arr) - 1 == self.N:
            # 若组合唯一，则直接计算出并返回，使用二进制存储涂色情况，1为涂色，0为不涂色
            # 先全部涂色后抹除
            temp = 2 ** (self.N + 1) - 1
            n = 0
            for e in reversed(arr):
                n += e
                temp -= 2 ** n
                n += 1
            return [temp]
        else:
            # 组合不唯一，详见下个函数的注释
            siteNum = len(arr) + 1
            spaceNum = self.N - sum(arr) - len(arr) + 1
            splitArr: list[int] = []
            self.__NSUM(splitArr, spaceNum, siteNum, arr)
            return splitArr

    def __NSUM(self, ans: list[int], tar: int, length: int, arr: list[int], cal=None, count: int = 0,
               template=None) -> None:
        """
        核心是一个全排列算法，TODO 可改为动态规划
        首先，空格子出现的位置有传入的数的个数+1个位置，即每个连续涂色格子的两端；
        其次，两个连续涂色的条之间必定有至少一个的空格子；
        最终，根据以上两个条件计算出自由的空格子份额，并将这些份额按照全排列的方式获取将自由空格子的个数分入
        可能为空格子的地方的所有分配方案，并加上[0,1,1...,0]向量，即为所有可能的空格子分配方案，然后与涂色
        格子组合，得出该行（列）的涂色方案，并将其压缩
        :param ans:空格子的所有可能分配组合
        :param tar:待分配自由空格子的数目
        :param length:连续空格子的数目
        :param arr: 初始传入的行（列）信息，用于计算待选组合
        :param cal:分配空格子的组合
        :param count:分配了的空格子数目
        :param template:一定的空格子[0,1,1,...1,0]
        :return:
        """
        # ------------初始化------------
        if cal is None:
            cal = []
        if template is None:
            # 根据填入数长度自行初始化，长度为2 则生成的为:[0,1,0]
            template: list[int] = [1] * length
            template[0] = 0
            template[len(template) - 1] = 0

        # ----------- 终止条件-------------
        if length == len(cal):
            if tar == count:
                temp = 0
                for j, k in zip(arr, [a + b for a, b in zip(template, cal)][1:]):
                    for x in range(j):
                        temp *= 2
                        temp += 1
                    temp *= 2 ** k
                ans.append(temp)
            return

        # ------------回溯------------
        for i in range(tar - count + 1):
            cal.append(i)
            self.__NSUM(ans, tar, length, arr, cal, count + i, template)
            cal.pop()


if __name__ == "__main__":
    n1 = Nonogram()
    n1.run()
